public class Solution416 {
    public int getSum(int[] nums){
        int sum=0;
        for (int num:nums) {
            sum+=num;
        }
        return sum;
    }

    public boolean canPartition(int[] nums) {
        int sum=getSum(nums);
        if(sum%2==1){
            return false;
        }
        int tar=sum/2;
        boolean[][] dp=new boolean[nums.length][tar+1];
        if(nums[0]<tar+1) {
            dp[0][nums[0]] = true;
        }
        for (int i = 1; i < dp.length; i++) {
            int tmpNum=nums[i];
            boolean[] tmp=dp[i];
            boolean[] last=dp[i-1];
            for (int j = 0; j <= tar; j++) {
                tmp[j]=last[j];
                if(j==tmpNum){
                    tmp[j]=true;
                }
                else if(j>tmpNum&&last[j-tmpNum]==true){
                    tmp[j]=true;
                }
            }
        }
        return dp[nums.length-1][tar];
    }
}
